<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>

  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
  <title>Safe Ownership-Based Memory Management</title>


  <meta content="Adam Dingle" name="author">

  <style type="text/css">
h1 { font-size: 18pt;
font-weight: bold;
font-family: Arial,Helvetica,sans-serif;
text-align: center;
}
.author { font-family: Arial,Helvetica,sans-serif;
font-size: 12pt;
text-align: center;
}
address { text-align: center;
font-family: Arial,Helvetica,sans-serif;
font-size: 10pt;
font-style: normal;
}
body {
font-size: 9pt;
}
h2 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h3 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h4 { font-family: Times New Roman,Times,serif;
font-size: 11pt;
font-style: italic;
font-weight: normal;
}
  </style>
</head>


<body>

<h2>PROPOSED EXTENSIONS<br>

</h2>

In this section we sketch a number of possible extensions to the Gel
language. We have not implemented any of these.<br>

<h2>Object Destruction</h2>

Gel's object destruction mechanism as outlined above has a number of
limitations:<br>

<ul>

  <li>Gel does not let the programmer define a <dfn>destructor</dfn>
for a
class, i.e. a method which will run when an instance of the class is
destroyed.</li>

  <li>Gel can automatically destroy structures in which each
internal non-owning pointer points to an ancestor in the ownership
tree, but cannot automatically destroy structures containing arbitrary
non-owning pointers to internal nodes.</li>

  <li>Object destruction in Gel may consume a large amount of
stack space since it is inherently recursive.</li>

</ul>

To overcome these limitations, we propose adding destructors to Gel,
and propose a multi-phase object destruction mechanism. Gel
could destroy an object graph rooted at a pointer P in the following
phases.<br>

<br>

1. Recursively descend all objects in the ownership tree below P,
running each object's destructor.<br>

2. Recursively descend again; for each non-owning pointer in every
object, decrement the reference count of the object pointed to.<br>

3. Recursively descend again; for each object, check that its reference
count is zero and free the object.<br>

<br>

In many cases the compiler should be able to optimize away some or all
of the work to be performed in the first and/or second phases.
In particular, using static type analysis it will often be
possible to determine that all objects in the graph below an object of
type T will never have any destructors or non-owning pointers; in that
case the first or second phases need not run at all below such objects.
As a simple example, consider a singly linked list in which
each node contains only an integer and an owning pointer to the next
node; then the first and second phases can be optimized away
entirelyin destroying a list of this type.<br>

<br>

Note also that in many structures each node contains only a single
owning pointer; in such structures, the compiler can save stack space
by eliminating tail recursion in generating the code to perform the
recursive descent in each phase. With these optimizations in
place, we believe that this generalized destruction algorithm might
outperform thealgorithm in the existing Gel implementation in
many cases.<br>

<br>

User-written destructors might potentially mutate the graph of objects
being destroyed. If a destructor inserts objects into the
graph, then these objects might be destroyed in phases 2 and 3 even
though their destructors have never run. Similarly, if a
destructor removes objects whose destructors have already run, then
those objects' destructors might run againwhen they are
destroyed at a later time. This possibility does not
compromise the safety of the language, but does mean that each object's
destructor is not guaranteed to run exactly once. It might be
possible to detect destructor-induced mutations in some way and report
an error if they occur; we will not discuss this possibility further
here.<br>

<h3>Polymorphism</h3>

The Gel type system does not support any sort of polymorphism between
owning and non-owning types. This means that it's not
possible to write a method which can receive either an owning or
non-owning pointer as an input parameter. It's also not
possible to implement a single data structure (such as a tree or hash
table) which can hold either owning or non-owning pointer.
This limitation is reflected in the Gel class library, which
contains separate ArrayList and NonOwningArrayList classes.<br>

<br>

It would be useful to extend Gel
withgeneric types as found in Java and C#, allowing a generic
type to represent either an owning or non-owning type. As a
simple example, suppose that we'd like to implement a class
Pair&lt;T&gt; which holds two objects of type T. We'd
like to be able to instantiate the class using either an owning or
non-owning pointer type. Our generic type system might allow
this as follows:<br>

<br>

class Pair&lt;T&gt; {<br>

T first_, second_;<br>

Pair(T first, T second) { first_ = first; second_ = second; }<br>

T% First() { return first_; }<br>

T% Second() { return second_; }<br>

}<br>

<br>

The system includes a type operator % which can be applied only to a
generic type, and which removes ownership from a type. In
particular, if T is Foo ^, then T% is Foo; if T is Foo, then T% is also
Foo.<br>

<br>

A generic type system for Gel should also support <dfn>covariance</dfn>:
it should be possible to write a single function which can take either
a Pair&lt;Foo&gt; or a Pair&lt;Foo ^&gt; as a
parameter, and similarly it should be possible to write a single
function which can take either a Foo[] or a Foo^[] as a parameter.<br>

<br>

We believe that it should not be difficult to design a complete
generics system for Gel including covariance, but we will not explore
the idea further in this work.<br>

<h2>Multithreading</h2>

As described above, the Gel compiler's reference count elimination
optimization will work only in single-threaded programs; this is a
significant limitation.<br>

<br>

It would be useful to extend Gel to be able to execute multithreaded
programs safely and efficiently. We can imagine two different
possible approaches here. First,it might be
possible to extend Gel'soptimizer to be able to infer that
many data structures are accessed only from a single thread; then
reference counts in such structures could be optimized away using the
existing algorithm. Such inference seems difficult and we are
relatively pessimistic about such an approach.<br>

<br>

As another
approach, we could possibly extend Gel so that objects are grouped
into <dfn>apartments</dfn>
which may be accessed from only a single thread at
once. With this approach, the existing optimization algorithm
could be used to eliminatereference count accesses in code
which
executes inside a single apartment. It might be possible to
designsystem which guarantees that only pointers of a certain
kind may cross apartment boundaries and which allows groups of objects
to move efficiently between apartments; we leave this to further work.<br>

</body>
</html>
